0074. 搜索二维矩阵【中等】
1. 🔗 links
- https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array/flat
- MDN -
Array.prototype.flat()- 将数组拍扁。
- MDN -
2. 📝 题目描述
给你一个满足下述两条属性的 m x n 整数矩阵:
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target,如果 target 在矩阵中,返回 true ;否则,返回 false。
示例 1:

输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出:true1
2
2
示例 2:

输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出:false1
2
2
提示:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-10^4 <= matrix[i][j], target <= 10^4
3. 🎯 s.1 - flat
javascript
var searchMatrix = function (matrix, target) {
return matrix.flat().includes(target)
}1
2
3
2
3
- 将二维数组转换为一维 -
Array.prototype.flat()- 将数组拍扁。
js
;[0, 1, 2, [3, 4]].flat() // => [0, 1, 2, 3, 4]
;[0, 1, 2, [[[3, 4]]]].flat(2) // => [0, 1, 2, [3, 4]]
// flat() 参数默认值为 11
2
3
2
3
4. 🎯 s.1 - 循环二维数组
javascript
var searchMatrix = function (matrix, target) {
const rows = matrix.length,
cols = matrix[0].length
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
const item = matrix[r][c]
if (item === target) return true
}
}
return false
}1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
- 两个 for 循环,暴力循环二维数组的每一项。
- 一旦发现与目标值 target 相等的项,则返回 true,表示在该二维数组 matrix 中找到了目标值。
- 若找完所有项都没找到与目标值相等的值,则返回 false,表明该二维数组 matrix 中不存在目标值。

5. 🎯 s.1 - 二分查找
javascript
var searchMatrix = function (matrix, target) {
const rows = matrix.length,
cols = matrix[0].length
let start = 0,
end = rows * cols - 1
while (start <= end) {
const mid = start + ((end - start) >> 1),
r = parseInt(mid / cols),
c = mid % cols,
item = matrix[r][c]
if (item === target) return true
else if (item < target) start = mid + 1
else end = mid - 1
}
return false
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
- 将二维数组视作一维数组来做,并且题目明确该二维数组是有序的。

